/*
34 Answers
Given an array of intergers. Write a program to print all the permutations of the numbers in the array. The output should be sorted in a non-increasing order. For example for the array { 12, 4, 66, 8, 9}, the output should be:

9866412

9866124

9846612

....

....

1246689
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap(int &a, int &b)
{
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

void dfs(int index, int A[], int size, vector<int> cur, vector<string> &ans)
{
    if (index == size) {
	ostringstream os;
        for (int i = 0; i < cur.size(); i++)
	    os << cur[i]; 
	ans.push_back(os.str());
	return;
    }

    for (int i = index; i < size; i++) {
	swap(A[index], A[i]);
	cur.push_back(A[index]);
	dfs(index+1, A, size, cur, ans);
	cur.pop_back();
	swap(A[index], A[i]);
    }
}

vector<string>  printCombination(int A[], int size)
{
    vector<string> ans;
    vector<int> cur;
    dfs(0, A, size, cur, ans); 
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
//    for (int i = 0; i < ans.size(); i++) 
//	cout << ans[i] << " ";
    cout << ans.size() << endl;
    return ans;
}


int main(int argc, char **argv)
{
    int A[] =  { 12, 4, 66, 8, 9};
    printCombination(A, sizeof(A)/sizeof(int)); 
}
